package com.njupt.Tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/11/29 13:55
 * @Description: 513. 找树左下角的值
 * @Version: 1.0
 */


public class FindBottomLeftValue {


    private int result;

    private int maxDepth = Integer.MIN_VALUE;


    public int findBottomLeftValue1(TreeNode root){
        traverse2(root,1);
        return result;
    }

    public void traverse(TreeNode root,int currentDepth){
        currentDepth++;
        if(root.left == null && root.right == null){
            if(currentDepth>this.maxDepth){
                this.maxDepth = currentDepth;
                this.result = root.val;
                return;
            }
        }
        if(root.left != null){
            traverse(root.left,currentDepth); //隐含了回溯
        }
        if(root.right != null){
            traverse(root.right,currentDepth);//隐含了回溯
        }

    }


    public void traverse1(TreeNode root,int currentDepth){

        if(root.left == null && root.right == null){
            if(currentDepth>this.maxDepth){
                this.maxDepth = currentDepth;
                this.result = root.val;
                return;
            }
        }
        if(root.left != null){
            currentDepth++;
            traverse1(root.left,currentDepth);
            currentDepth--;                    //回溯
        }
        if(root.right != null){
            currentDepth++;
            traverse1(root.right,currentDepth);
            currentDepth--;                    //回溯
        }


    }

    public void traverse2(TreeNode root,int currentDepth){

        if(root.left == null && root.right == null){
            if(currentDepth>this.maxDepth){
                this.maxDepth = currentDepth;
                this.result = root.val;
                return;
            }
        }
        if(root.left != null){
            traverse1(root.left,currentDepth+1);
        }
        if(root.right != null){
            traverse1(root.right,currentDepth+1);
        }


    }

    /**
     * 先序遍历非递归算法
     * @param root
     * @return
     */
    public int findBottomLeftValue(TreeNode root) {
        int maxDepth =  0;
        int currentDepth = 0;
        int result = root.val;

        Deque<TreeNode> treeStack = new LinkedList<>();
        Deque<Integer> depthStack = new LinkedList<>();
        TreeNode cur = root;
        while(cur != null || !treeStack.isEmpty()){
            if(cur != null){
                //访问根节点

                treeStack.push(cur);
                depthStack.push(++currentDepth);
                if(currentDepth>maxDepth){
                    maxDepth = currentDepth;
                    result = cur.val;
                }


                cur = cur.left;
            }else {
                cur = treeStack.pop();
                currentDepth = depthStack.pop();
                cur = cur.right;
            }
        }
        return result;

    }



    public static void main(String[] args) {
//        TreeNode root = new TreeNode(2);
//        root.left = new TreeNode(1);
//        root.right = new TreeNode(3);

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.right.left = new TreeNode(5);
        root.right.left.left = new TreeNode(7);
        root.right.right = new TreeNode(6);
        FindBottomLeftValue test = new FindBottomLeftValue();
        System.out.println(test.findBottomLeftValue1(root));
    }
}
